package com.atguigu.kmp;

import java.util.Arrays;

public class KMPAlgorithm {

    public static void main(String[] args)
    {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
		String str2 = "ABCDABD";
		//String str2 = "BBC";
		
		int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
		System.out.println("next=" + Arrays.toString(next));

        System.out.println("------------>" );

        int index = kmpSearch(str1, str2, next);
		System.out.println("index=" + index);
    }


    // 获取kmp前缀列
    public static int[] kmpNext(String str)
    {

        int[]  next=new int[str.length()];
        next[0]=0;
        for(int i=1,j=0;i<str.length();i++)
        {
            if(str.charAt(i)!=str.charAt(j))
            {
                next[i]=0;
                j=0;
            }
            if(str.charAt(i)==str.charAt(j))
            {
                j++;
            }
            next[i]=j;
        }
        return next;
    }
    

    public static int  kmpSearch(String str1,String str2,int[] next)
    {
        int j=0;
        int i=0;
        while(i<str1.length()&&j<str2.length())
        {
            System.out.println("index=" + i);
            // 计算出当时匹配数
            if(str1.charAt(i)==str2.charAt(j))
            {
                j++;
                i++;
            } else {
                  // 计算出当时往后移动数
                int s= j-next[j]+i;
                if(s==i)
                {
                    i++;
                } else {
                    i=s-1;
                }

               // i++;
                j=0;
                
               
            }
           
        }
        if(j==str2.length())
        {
            return i-j;
        }else {
            return -1;
        }

    }

    
}